import java.util.HashSet;

/**
 * 排列组合的方法也比较固定：
 * 第一种，类似于动态规划的方法，即保存中间结果，依次附上新元素
 * 第二种，是递归，通常实在递归函数里面使用for循环，遍历所有排列或组合的可能，然后在for循环语句内调用递归函数
 */

/**
 * 打印数字的排列组合方式的最简单的方法就是递归，但本题存在两个难点：一是数字中存在重复数字，二是明确规定了某些位的特性。
 * 显然，采用常规的求解方法似乎不能完全适用。
 * 其实，可以换一种思维，把求解这6 个数字的排列组合问题转换为对大家都熟悉的图的遍历问题，解答起来就容易多了。
 * 可以把1、2、2、3、4、5这6个数看成是图的6个结点，对这6个结点两两相连可以组成一个无向连通图，
 * 这6个数对应的全排列等价于从这个图中各个结点出发深度优先遍历这个图中所有可能路径所组成的数字集合。
 * 例如，从结点“1”出发所有的遍历路径组成了以“1”开头的所有数字的组合。
 * 由于“3”与“5”不能相连，因此在构造图时使图中“3”和“5”对应的结点不连通就可以满足这个条件。
 * 对于“4”不能在第三位，可以在遍历结束后判断是否满足这个条件。
 * 具体而言，实现步骤如下：1）用1、2、2、3、4、5这6个数作为6个结点，构造一个无向连通图。
 * 除了“3”与“5”不连通外，其他的所有结点都两两相连。2）分别从这6个结点出发对图做深度优先遍历。
 * 每次遍历完所有结点时，把遍历的路径对应数字的组合记录下来，如果这个数字的第三位不是“4”，则把这个数字存放到集
 */
public class A如何求数字的组合 {
    private int nummbers[] = {1, 2, 2, 3, 4, 5};
    private int n = 6;
    /**
     * 用来标记图中节点是否被遍历过
     */
    private boolean[] visited;
    /**
     * 图的二维数组表示
     */
    private int[][] graph;
    /**
     * 数字组合
     */
    private StringBuffer combination = new StringBuffer();
    /**
     * 存放所有的组合
     */
    private HashSet<String> s = new HashSet<String>();

    public A如何求数字的组合(int[] arr) {
        nummbers = arr;
        visited = new boolean[nummbers.length];
        graph = new int[nummbers.length][nummbers.length];
    }

    private void depthFirstSearch(int start) {
        visited[start] = true;
        combination.append(nummbers[start]);
        if (combination.length() == n) {
            if (combination.indexOf("4") != 2) {
                s.add(combination.toString());
            }
        }
        for (int j = 0; j < n; j++) {
            if (graph[start][j] == 1 && !visited[j]) {
                depthFirstSearch(j);
            }
        }
        combination.delete(combination.length() - 1, combination.length());
        visited[start] = false;
    }

    public void getAllCombinations() {
        int i;
        for (i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    graph[i][j] = 0;
                } else {
                    graph[i][j] = 1;
                }
            }
        }
        //确保在遍历的时候3与5是不可达的
        graph[3][5] = 0;
        graph[5][3] = 0;
        for (i = 0; i < n; i++) {
            depthFirstSearch(i);
        }
    }

    public void printAllCombinations() {
        for (String str : s) {
            System.out.println(str);
        }
    }


    public static void main(String[] args) {
        /**
         * 可以把1、2、2、3、4、5这6个数看成是图的6个结点，对这6个结点两两相连可以组成一个无向连通图，
         * 这6个数对应的全排列等价于从这个图中各个结点出发深度优先遍历这个图中所有可能路径所组成的数字集合
         */
        int[] arr = {1, 2, 2, 3, 4, 5};
        A如何求数字的组合 t = new A如何求数字的组合(arr);
        t.getAllCombinations();
        t.printAllCombinations();
    }
}